package main

import (
	"fmt"
)

/*
输入一个n 一个k
有一个数组n个元素 a1,a2,...,an 表示第i天爬山可以获得的娱乐值，
规则是如果前一天爬了山，第二天就不能再爬
但是一共有k次打破规则的机会
问如何安排爬山可以获得最大的娱乐值

输入：
n=7 k=1
a = [1,2,3,4,5,6,7]
输出：
19 => 安排2，4，6，7爬山
*/

func main() {
	n := 7
	k := 1
	a := []int{0, 1, 2, 3, 4, 5, 6, 7} // 多加一位，从i=1开始
	res := climb(n, k, a)
	fmt.Println(res)
}

func climb(n, k int, a []int) int {
	// dp[i][j][0/1]表示第i天，已打破规则j次，今天不爬/爬 的最大娱乐值
	// 第i天不选择爬山： dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j][1])  意味着昨天不爬或昨天爬都可，今天直接休息
	// 第i天选择爬山： dp[i][j][1] = dp[i-1][j][0]+a[i] 只能从i-1天不爬山转移过来
	// 第i天爬山并打破规则(j>0还有打破规则的机会)： 从i-1天爬
	// dp[i][j][1] = max(dp[i-1][j][0] + a[i], dp[i-1][j-1][1] + a[i])
	dp := make([][][]int, n+1) // 多加一位，从i=1开始
	for i := 0; i <= n; i++ {
		dp[i] = make([][]int, k+1) // 多加一位，从k=1开始
		for j := 0; j <= k; j++ {
			dp[i][j] = make([]int, 2)
		}
	}
	for i := 1; i <= n; i++ {
		for j := 0; j <= k; j++ {
			dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j][1])
			dp[i][j][1] = dp[i-1][j][0] + a[i]
			if j > 0 {
				dp[i][j][1] = max(dp[i][j][1], dp[i-1][j-1][1]+a[i])
			}
		}
	}
	return max(dp[n][k][0], dp[n][k][1])
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}
